<!DOCTYPE html>
<html>
  <head>
    <title>Lazy Evaluation</title>
    <link rel="stylesheet" type="text/css" href="style.css">
      </head>
  <body>
    <h1>Lazy Evaluation</h1>
<p>The 'lazy' vocabulary adds lazy lists to Factor. This provides the
    ability to describe infinite structures, and to delay execution of
    expressions until they are actually used.</p>
<p>Lazy lists, like normal lists, are composed of a head and tail. In
    a lazy list the head and tail are something called a 'promise'. 
    To convert a
    'promise' into its actual value a word called 'force' is used. To
    convert a value into a 'promise' the word to use is 'delay'.</p>
<table border="1">
<tr><td><a href="#delay">delay</a></td></tr>
<tr><td><a href="#force">force</a></td></tr>
</table>

<p>Many of the lazy list words are named similar to the standard list
    words but with an 'l' prefixed to it. Here are the commonly used
    words and their equivalent list operation:</p>
<table border="1">
<tr><th>Lazy List</th><th>Normal List</th></tr>
<tr><td><a href="#lnil">lnil</a></td><td>[ ]</td></tr>
<tr><td><a href="#lnilp">lnil?</a></td><td>Test for nil value</td></tr>
<tr><td><a href="#lcons">lcons</a></td><td>cons</td></tr>
<tr><td><a href="#lunit">lunit</a></td><td>unit</td></tr>
<tr><td><a href="#lcar">lcar</a></td><td>car</td></tr>
<tr><td><a href="#lcdr">lcdr</a></td><td>cdr</td></tr>
<tr><td><a href="#lnth">lnth</a></td><td>nth</td></tr>
<tr><td><a href="#luncons">luncons</a></td><td>uncons</td></tr>
<tr><td><a href="#lmap">lmap</a></td><td>map</td></tr>
<tr><td><a href="#lsubset">lsubset</a></td><td>subset</td></tr>
<tr><td><a href="#leach">leach</a></td><td>each</td></tr>
<tr><td><a href="#lappend">lappend</a></td><td>append</td></tr>
</table>
<p>A few additional words specific to lazy lists are:</p>
<table border="1">
<tr><td><a href="#ltake">ltake</a></td><td>Returns a normal list containing a specified
number of items from the lazy list.</td></tr>
<tr><td><a href="#lappendstar">lappend*</a></td><td>Given a lazy list of lazy lists,
concatenate them together in a lazy manner, returning a single lazy
list.</td></tr>
<tr><td><a href="#list>llist">list>llist</a></td><td>Given a normal list, return a lazy list
that contains the same elements as the normal list.</td></tr>
</table>
<h2>Reference</h2>
<!-- delay description -->
<a name="delay">
<h3>delay ( quot -- &lt;promise&gt; )</h3>
<p>'delay' is used to convert a value or expression into a promise.
   The word 'force' is used to convert that promise back to its
   value, or to force evaluation of the expression to return a value.
</p>
<p>The value on the stack that 'delay' expects must be quoted. This is
   a requirement to prevent it from being evaluated.
</p>
<pre class="code">
  ( 1 ) [ 42 ] <a href="#delay">delay</a> dup .
       => &lt;&lt; promise [ ] [ 42 ] [ ] [ ] &gt;&gt;
  ( 2 ) <a href="#force">force</a> .
       => 42
</pre>

<!-- force description -->
<a name="force">
<h3>force ( &lt;promise&gt; -- value )</h3>
<p>'force' will evaluate a promises original expression
   and leave the value of that expression on the stack.
</p>
<p>A promise can be forced multiple times but the expression
   is only evaluated once. Future calls of 'force' on the promise
   will returned the cached value of the original force. If the
   expression contains side effects, such as i/o, then that i/o
   will only occur on the first 'force'. See below for an example
   (steps 3-5).
</p>
<p>If a promise is itself delayed, a force will evaluate all promises
   until a value is returned. Due to this behaviour it is generally not
   possible to delay a promise. The example below shows what happens
   in this case.
</p>
<pre class="code">       
  ( 1 ) [ 42 ] <a href="#delay">delay</a> dup .
       => &lt;&lt; promise [ ] [ 42 ] [ ] [ ] &gt;&gt;
  ( 2 ) <a href="#force">force</a> .
       => 42
       
        #! Multiple forces on a promise returns cached value
  ( 3 ) [ "hello" print 42 ] <a href="#delay">delay</a> dup .
       => << promise [ ] [ "hello" print 42 ] [ ] [ ] >>
  ( 4 ) dup <a href="#force">force</a> .
       => hello
          42
  ( 5 ) <a href="#force">force</a> .
       => 42

        #! Forcing a delayed promise cascades up to return
        #! original value, rather than the promise.
  ( 6 ) [ [ 42 ] <a href="#delay">delay</a> ] <a href="#delay">delay</a> dup .
       => << promise [ ] [ [ 42 ] delay ] [ ] [ ] >>
  ( 7 ) <a href="#force">force</a> .
       => 42
</pre>

<!-- lnil description -->
<a name="lnil">
<h3>lnil ( -- lcons )</h3>
<p>Returns a value representing the empty lazy list.</p>
<pre class="code">
  ( 1 ) <a href="#lnil">lnil</a> .
       => << promise [ ] [ [ ] ] t [ ] >>
</pre>

<!-- lnil description -->
<a name="lnilp">
<h3>lnil? ( lcons -- bool )</h3>
<p>Returns true if the given lazy cons is the value representing 
   the empty lazy list.</p>
<pre class="code">
  ( 1 ) <a href="#lnil">lnil</a> <a href="#lnilp">lnil?</a> .
       => t
  ( 2 ) [ 1 ] <a href="#list2llist">list&gt;llist</a> dup <a href="#lnilp">lnil?</a> .
       => [ ]
  ( 3 ) <a href="#lcdr">lcdr</a> <a href="#lnilp">lnil?</a> .
       => t
</pre>

<!-- lcons description -->
<a name="lcons">
<h3>lcons ( car-promise cdr-promise -- lcons )</h3>
<p>Provides the same effect as 'cons' does for normal lists. 
   Both values provided must be promises (ie. expressions that have
   had <a href="#delay">delay</a> called on them).
</p>
<p>As the car and cdr passed on the stack are promises, they are not
   evaluated until <a href="#lcar">lcar</a> or <a href="#lcdr">lcdr</a>
   are called on the lazy cons.</p>
<pre class="code">
  ( 1 ) [ "car" ] <a href="#delay">delay</a> [ "cdr" ] <a href="#delay">delay</a> <a href="#lcons">lcons</a> dup .
       => &lt;&lt; promise ... &gt;&gt;
  ( 2 ) dup <a href="#lcar">lcar</a> .
       => "car"
  ( 3 ) dup <a href="#lcdr">lcdr</a> .
       => "cdr"
</pre>
  
<!-- lunit description -->
<a name="lunit">
<h3>lunit ( value-promise -- llist )</h3>
<p>Provides the same effect as 'unit' does for normal lists. It
creates a lazy list where the first element is the value given.</p>
<p>Like <a href="#lcons">lcons</a>, the value on the stack must be
   a promise and is not evaluated until the <a href="#lcar">lcar</a>
   of the list is requested.</a>
<pre class="code">
  ( 1 ) [ 42 ] <a href="#delay">delay</a> <a href="#lunit">lunit</a> dup .
       => &lt;&lt; promise ... &gt;&gt;
  ( 2 ) dup <a href="#lcar">lcar</a> .
       => 42
  ( 3 ) dup <a href="#lcdr">lcdr</a> <a href="#lnilp">lnil?</a> .
       => t
  ( 4 ) [ . ] <a href="#leach">leach</a>
       => 42
</pre>

<!-- lcar description -->
<a name="lcar">
<h3>lcar ( lcons -- value )</h3>
<p>Provides the same effect as 'car' does for normal lists. It
returns the first element in a lazy cons cell. This will force
the evaluation of that element.</p>
<pre class="code">
  ( 1 ) [ 42 ] <a href="#delay">delay</a> <a href="#lunit">lunit</a> dup .
       => &lt;&lt; promise ... &gt;&gt;
  ( 2 ) <a href="#lcar">lcar</a> .
       => 42
</pre>

<!-- lcdr description -->
<a name="lcdr">
<h3>lcdr ( lcons -- value )</h3>
<p>Provides the same effect as 'cdr' does for normal lists. It
returns the second element in a lazy cons cell and forces it. This
causes that element to be evaluated immediately.</p>
<pre class="code">
  ( 1 ) [ 1 ] <a href="#delay">delay</a> [ 5 6 + ] <a href="#delay">delay</a> <a href="#lcons">lcons</a> dup .
       => &lt;&lt; promise ... &gt;&gt;
  ( 2 ) <a href="#lcdr">lcdr</a> .
       => 11
</pre>

<pre class="code">
  ( 1 ) 5 <a href="#lfrom">lfrom</a> dup .
       => &lt;&lt; promise ... &gt;&gt;
  ( 2 ) <a href="#lcdr">lcdr</a> dup <a href="#lcar">lcar</a> .
       => 6
  ( 3 ) <a href="#lcdr">lcdr</a> dup <a href="#lcar">lcar</a> .
       => 7
  ( 4 ) <a href="#lcdr">lcdr</a> dup <a href="#lcar">lcar</a> .
       => 8
</pre>

<!-- lnth description -->
<a name="lnth">
<h3>lnth ( n llist -- value )</h3>
<p>Provides the same effect as 'nth' does for normal lists. It
returns the nth value in the lazy list. It causes all the values up to
'n' to be evaluated.</p>
<pre class="code">
  ( 1 ) 1 <a href="#lfrom">lfrom</a> dup .
       => &lt;&lt; promise ... &gt;&gt;
  ( 2 ) 5 swap <a href="#lnth">lnth</a> .
       => 6
</pre>

<!-- luncons description -->
<a name="luncons">
<h3>luncons ( lcons -- car cdr )</h3>
<p>Provides the same effect as 'uncons' does for normal lists. It
returns the car and cdr of the lazy list.</p>
<pre class="code">
  ( 1 ) [ 5 ] <a href="#delay">delay</a> [ 6 ] <a  href="#delay">delay</a> <a href="#lcons">lcons</a> dup .
       => &lt;&lt; promise ... &gt;&gt;
  ( 2 ) <a href="#luncons">luncons</a> . .
       => 6
          5
</pre>

<!-- lmap description -->
<a name="lmap">
<h3>lmap ( llist quot -- llist )</h3>
<p>Lazily maps over a lazy list applying the quotation to each element.
A new lazy list is returned which contains the results of the
quotation.</p>
<p>When intially called nothing in the original lazy list is
evaluated. Only when <a href="#lcar">lcar</a> is called will the item
in the list be evaluated and applied to the quotation. Ditto with <a
href="#lcdr">lcdr</a>, thus allowing infinite lists to be mapped over.</p>
<pre class="code">
  ( 1 ) 1 <a href="#lfrom">lfrom</a>
       => < infinite list of incrementing numbers >
  ( 2 ) [ 2 * ] <a href="#lmap">lmap</a>
       => < infinite list of numbers incrementing by 2 >
  ( 3 ) 5 swap <a href="#ltake">ltake</a> <a  href="#llist2list">llist&gt;list</a> .
       => [ 2 4 6 8 10 ]
</pre>

<!-- lsubset description -->
<a name="lsubset">
<h3>lsubset ( llist pred -- llist )</h3>
<p>Provides the same effect as 'subset' does for normal lists. It
lazily iterates over a lazy list applying the predicate quotation to each
element. If that quotation returns true, the element will be included
in the resulting lazy list. If it is false, the element will be skipped.
A new lazy list is returned which contains  all elements where the
predicate returned true.</p>
<p>Like <a href="#lmap">lmap</a>, when initially called no evaluation
will occur. A lazy list is returned that when values are retrieved
from in then items are evaluated and checked against the predicate.</p>
<pre class="code">
  ( 1 ) 1 <a href="#lfrom">lfrom</a>
       => < infinite list of incrementing numbers >
  ( 2 ) [ <a href="#primep">prime?</a> ] <a href="#lsubset">lsubset</a>
       => < infinite list of prime numbers >
  ( 3 ) 5 swap <a href="#ltake">ltake</a> <a  href="#llist2list">llist&gt;list</a> .
       => [ 2 3 5 7 11 ]
</pre>

<!-- leach description -->
<a name="leach">
<h3>leach ( llist quot --  )</h3>
<p>Provides the same effect as 'each' does for normal lists. It
lazily iterates over a lazy list applying the quotation to each
element. If this operation is applied to an infinite list it will
never return unless the quotation escapes out by calling a continuation.</p>
<pre class="code">
  ( 1 ) 1 <a href="#lfrom">lfrom</a>
       => < infinite list of incrementing numbers >
  ( 2 ) [ 2 mod 1 = ] <a href="#lsubset">lsubset</a>
       => < infinite list of odd numbers >
  ( 3 ) [ . ] <a href="#leach">leach</a> 
       => 1
          3
          5
          7
          ... for ever ...
</pre>

<!-- ltake description -->
<a name="ltake">
<h3>ltake ( n llist -- llist )</h3>
<p>Iterates over the lazy list 'n' times, appending each element to a
lazy list. This provides a convenient way of getting elements out of
an infinite lazy list.</p>
<pre class="code">
  ( 1 ) : ones [ 1 ] delay [ ones ] delay <a href="#lcons">lcons</a> ;
  ( 2 ) 5 ones <a href="#ltake">ltake</a> <a  href="#llist2list">llist&gt;list</a> .
       => [ 1 1 1 1 1  ]
</pre>

<!-- lappend description -->
<a name="lappend">
<h3>lappend ( llist1 llist2 -- llist )</h3>
<p>Lazily appends two lists together. The actual appending is done
lazily on iteration rather than immediately so it works very fast no
matter how large the list.</p>
<pre class="code">
  ( 1 ) [ 1 2 3 ] <a href="#list2llist">list&gt;llist</a> [ 4 5 6 ] <a href="#list2llist">list&gt;llist</a> <a href="#lappend">lappend</a>
  ( 2 ) [ . ] <a href="#leach">leach</a>
       => 1
          2
          3
          4
          5
          6
</pre>

<!-- lappend* description -->
<a name="lappendstar">
<h3>lappend* ( llists -- llist )</h3>
<p>Given a lazy list of lazy lists, concatenate them together in a
lazy fashion. The actual appending is done lazily on iteration rather
than immediately so it works very fast no matter how large the lists.</p>
<pre class="code">
  ( 1 ) [ 1 2 3 ] <a href="#list2>llist">list&gt;llist</a> 
  ( 2 ) [ 4 5 6 ] <a href="#list2llist">list&gt;llist</a> 
  ( 3 ) [ 7 8 9 ] <a href="#list2llist">list&gt;llist</a>
  ( 4 ) 3list <a href="#list2llist">list&gt;llist</a> <a href="#lappendstar">lappend*</a>
  ( 5 ) [ . ] <a href="#leach">leach</a>
       => 1
          2
          3
          4
          5
          6
          7
          8
          9
</pre>

<!-- list>llist description -->
<a name="list2llist">
<h3>list&gt;llist ( list  -- llist )</h3>
<p>Converts a normal list into a lazy list. This is done lazily so the
initial list is not iterated through immediately.</p>
<pre class="code">
  ( 1 ) [ 1 2 3 ] <a href="#list2llist">list&gt;llist</a> 
  ( 2 ) [ . ] <a href="#leach">leach</a>
       => 1
          2
          3
</pre>

<p class="footer">
News and updates to this software can be obtained from the authors
weblog: <a href="http://radio.weblogs.com/0102385">Chris Double</a>.</p>
<p id="copyright">Copyright (c) 2004, Chris Double. All Rights Reserved.</p>
</body> </html>
